class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len = nums.size();
        vector<int> ret;
        deque<int> mydeque; //维护一个非递增双端队列
        int left = 0, right = left + k;
        for (int i = left; i < right; i++)  //初始化双端队列
        {
            while (!mydeque.empty() && nums[i] > mydeque.back())
                mydeque.pop_back();

            mydeque.push_back(nums[i]);
        }
        ret.push_back(mydeque.front());

        while (right < len)
        {
            if (nums[left++] == mydeque.front())
                mydeque.pop_front();
                
            right++;
            while (!mydeque.empty() && nums[right - 1] > mydeque.back())
                mydeque.pop_back();

            mydeque.push_back(nums[right - 1]);
            ret.push_back(mydeque.front());
        }

        return ret;
    }
};